/**
 * @param {number[]} nums
 * @return {number}
 */
var maxCoins = function (nums) {
  if (!nums || nums.length === 0) return 0

  //数组长度
  let n = nums.length
  //重构数组nums
  const balloons = new Array(n + 2).fill(1)
  for (let i = 0; i < n; i++) {
    balloons[i + 1] = nums[i]
  }

  //创建状态数组dp
  const dp = new Array(n + 2).fill(1).map(item => new Array(n + 2).fill(0))
  /* 遍历区间长度：
      2保证[i,j]之间只有一个气球，并且这个气球是最后被戳破的
      n+1保证[0,6]之间所有气球都有可能是最后一个被戳破的 */
  for (let len = 2; len <= n + 1; len++) {
    //遍历左边界
    for (let i = 0; i <= n + 1 - len; i++) {
      //计算右边界
      let j = i + len
      //遍历k：k是区间[i,j]之间最后一个被戳破的气球
      for (let k = i + 1; k < j; k++) {
        dp[i][j] = Math.max(
          dp[i][j],
          dp[i][k] + dp[k][j] + balloons[i] * balloons[k] * balloons[j]
        )
      }
    }
  }

  //返回结果
  return dp[0][n + 1]
};

maxCoins([1, 2, 3, 4, 5])